{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Time for Given Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestTimeFromDigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给定数字能组成的最大时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。</p>\n",
    "\n",
    "<p>24 小时格式为 <code>\"HH:MM\"</code> ，其中 <code>HH</code> 在 <code>00</code> 到 <code>23</code> 之间，<code>MM</code> 在 <code>00</code> 到 <code>59</code> 之间。最小的 24 小时制时间是 <code>00:00</code> ，而最大的是 <code>23:59</code> 。从 00:00 （午夜）开始算起，过得越久，时间越大。</p>\n",
    "\n",
    "<p>以长度为 5 的字符串，按 <code>\"HH:MM\"</code> 格式返回答案。如果不能确定有效时间，则返回空字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4]\n",
    "<strong>输出：</strong>\"23:41\"\n",
    "<strong>解释：</strong>有效的 24 小时制时间是 \"12:34\"，\"12:43\"，\"13:24\"，\"13:42\"，\"14:23\"，\"14:32\"，\"21:34\"，\"21:43\"，\"23:14\" 和 \"23:41\" 。这些时间中，\"23:41\" 是最大时间。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [5,5,5,5]\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>不存在有效的 24 小时制时间，因为 \"55:55\" 无效。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,0,0,0]\n",
    "<strong>输出：</strong>\"00:00\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0,0,1,0]\n",
    "<strong>输出：</strong>\"10:00\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr.length == 4</code></li>\n",
    "\t<li><code>0 <= arr[i] <= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-time-for-given-digits](https://leetcode.cn/problems/largest-time-for-given-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-time-for-given-digits](https://leetcode.cn/problems/largest-time-for-given-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[5,5,5,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort()\n",
    "        hourtenthdigit = [0, 1, 2]\n",
    "        hourdigit = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "        minutetenthdigit = [0,1,2,3,4,5]\n",
    "        minutedigit = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "        ans = ''\n",
    "        for i in hourtenthdigit:\n",
    "            for j in hourdigit:\n",
    "                if i == 2 and j > 3:\n",
    "                    break\n",
    "                for k in minutetenthdigit:\n",
    "                    for l in minutedigit:\n",
    "                        tmp = [i, j, k, l]\n",
    "                        if sorted(tmp) == arr:\n",
    "                            ans = str(tmp[0]) + str(tmp[1]) + ':' + str(tmp[2]) + str(tmp[3])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        hoursRes = -1\n",
    "        minsRes = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "                hoursRes = hours\n",
    "                minsRes = mins\n",
    "\n",
    "        return \"{:02}:{:02}\".format(hoursRes,minsRes) if ans >= 0 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        r,c=0,0\n",
    "        for t in list(set(permutations(arr))):\n",
    "            h,m=t[0]*10+t[1],t[2]*10+t[3]\n",
    "            if h>23 or m>59:continue\n",
    "            r,c=max(r,h*100+m),c+1\n",
    "        return '%02d:%02d'%(r//100,r%100) if c else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hour = 10 * h1 + h2\n",
    "            minutes = 10 * m1 + m2\n",
    "            time = 60 * hour + minutes\n",
    "            if 0 <= hour < 24 and 0 <= minutes < 60 and time > ans:\n",
    "                ans = time\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans > -1 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestTimeFromDigits(self, A):\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(A):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, A):\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(A):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\"\n",
    "\n",
    "# 作者：LeetCode\n",
    "# 链接：https://leetcode.cn/problems/largest-time-for-given-digits/solutions/15986/gei-ding-shu-zi-neng-zu-cheng-de-zui-da-shi-jian-b/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, A: List[int]) -> str:\n",
    "        X = []\n",
    "        for a in range(len(A)):\n",
    "            for b in range(len(A)):\n",
    "                if a != b:\n",
    "                    for c in range(len(A)):\n",
    "                        if a != c and b != c:\n",
    "                            for d in range(len(A)):\n",
    "                                if a != d and b != d and c != d:\n",
    "                                    X.append(str(A[a]) + str(A[b]) + str(A[c]) + str(A[d]))\n",
    "        valid_time = [i for i in X if int(i[0:2]) < 24 and int(i[2:4]) < 60]\n",
    "        if len(valid_time) == 0:\n",
    "            return ''\n",
    "        max_time = '-1'\n",
    "        for i in valid_time:\n",
    "            if int(i) > int(max_time):\n",
    "                max_time = i\n",
    "        return str(max_time[0:2]) + ':' + str(max_time[2:4])\n",
    "        \n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, A: List[int]) -> str:\n",
    "        X = []\n",
    "        for a in range(len(A)):\n",
    "            for b in range(len(A)):\n",
    "                if a != b:\n",
    "                    for c in range(len(A)):\n",
    "                        if a != c and b != c:\n",
    "                            for d in range(len(A)):\n",
    "                                if a != d and b != d and c != d:\n",
    "                                    X.append(str(A[a]) + str(A[b]) + str(A[c]) + str(A[d]))\n",
    "        valid_time = [i for i in X if int(i[0:2]) < 24 and int(i[2:4]) < 60]\n",
    "        if len(valid_time) == 0:\n",
    "            return ''\n",
    "        max_time = '-1'\n",
    "        for i in valid_time:\n",
    "            if int(i) > int(max_time):\n",
    "                max_time = i\n",
    "        return str(max_time[0:2]) + ':' + str(max_time[2:4])\n",
    "        \n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        max_hours, max_mins = -1, -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hour = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = hour * 60 + mins\n",
    "            if hour < 24 and mins < 60 and time > ans:\n",
    "                ans = time\n",
    "                max_hours, max_mins = hour, mins\n",
    "\n",
    "        return f\"{max_hours:02}:{max_mins:02}\" if ans>=0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        self.ans, rem = -1, {0, 1, 2, 3}\n",
    "        def dfs(idx, tmp):\n",
    "            if idx == 4: self.ans = max(self.ans, tmp)\n",
    "            else:\n",
    "                for v in range(4):\n",
    "                    if v in rem:\n",
    "                        rem.remove(v)\n",
    "                        new = tmp * 10 + arr[v]\n",
    "                        if idx == 0 and arr[v] < 3: dfs(idx + 1, new)\n",
    "                        elif idx == 1 and new < 24: dfs(idx + 1, new)\n",
    "                        elif idx == 2 and arr[v] < 6: dfs(idx + 1, new)\n",
    "                        elif idx == 3 and new % 100 < 60: dfs(idx + 1, new)\n",
    "                        rem.add(v)\n",
    "        dfs(0, 0)\n",
    "        if self.ans < 0: return ''\n",
    "        p1, p2 = str(self.ans // 100), str(self.ans % 100)\n",
    "        if len(p1) == 1: p1 = '0' + p1\n",
    "        if len(p2) == 1: p2 = '0' + p2\n",
    "        return p1 + ':' + p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        res = -1\n",
    "        for a, b, c, d in itertools.permutations(arr, 4):\n",
    "            if a * 10 + b < 24 and c * 10 + d < 60:\n",
    "                res = max(res, a*1000 + b*100 + c*10 + d)\n",
    "        return \"\" if res == -1 else \"{:>02d}:{:>02d}\".format(res // 100, res % 100) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort(reverse=True)\n",
    "        for a, b, c, d in permutations(arr):\n",
    "            if a * 10 + b < 24 and c * 10 + d < 60:\n",
    "                return f\"{a}{b}:{c}{d}\"\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort(reverse=True)\n",
    "        for a, b, c, d in permutations(arr):\n",
    "            if a * 10 + b < 24 and c * 10 + d < 60:\n",
    "                return f\"{a}{b}:{c}{d}\"\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, A: List[int]) -> str:\n",
    "        X = []\n",
    "        for a in range(len(A)):\n",
    "            for b in range(len(A)):\n",
    "                if a != b:\n",
    "                    for c in range(len(A)):\n",
    "                        if a != c and b != c:\n",
    "                            for d in range(len(A)):\n",
    "                                if a != d and b != d and c != d:\n",
    "                                    X.append(str(A[a]) + str(A[b]) + str(A[c]) + str(A[d]))\n",
    "        valid_time = [i for i in X if int(i[0:2]) < 24 and int(i[2:4]) < 60]\n",
    "        if len(valid_time) == 0:\n",
    "            return ''\n",
    "        max_time = '-1'\n",
    "        for i in valid_time:\n",
    "            if int(i) > int(max_time):\n",
    "                max_time = i\n",
    "        return str(max_time[0:2]) + ':' + str(max_time[2:4])\n",
    "        \n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = ''\n",
    "        arr = list(map(str, arr))\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            h = h1 + h2\n",
    "            m = m1 + m2\n",
    "            if int(h) < 24 and int(m) < 60 and h + m > ans:\n",
    "                ans = h + m\n",
    "        if not ans: return ''\n",
    "        return ans[:2] + ':' + ans[2:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = (-1, 0, 0, 0)\n",
    "        for time in permutations(arr):\n",
    "            # 检查正确性\n",
    "            if time[0] > 2 or time[0] == 2 and time[1] > 3 or time[2] > 5:\n",
    "                continue\n",
    "            # 与答案比较\n",
    "            if time > ans:\n",
    "                ans = time\n",
    "\n",
    "        a, b, c, d = ans\n",
    "        if a == -1:     # 一个正确的也没有\n",
    "            return ''\n",
    "        return f'{a}{b}:{c}{d}'\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        max_time = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = h1 * 10 + h2\n",
    "            minutes = m1 * 10 + m2\n",
    "            if hours < 24 and minutes < 60:\n",
    "                t = 3600 * hours + minutes * 60\n",
    "                max_time = max(max_time, t)\n",
    "        \n",
    "        if max_time == -1:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return \"{:02d}:{:02d}\".format(max_time // 3600, (max_time//60) % 60)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力，全排列，24种时间\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort(reverse=True)\n",
    "        arr = [str(i) for i in arr]\n",
    "        global ans\n",
    "        ans = ''\n",
    "        def backtrace(run, res):\n",
    "            global ans\n",
    "            if ans:\n",
    "                return\n",
    "            if run >= '2400':\n",
    "                return\n",
    "            if not res:\n",
    "                if run[2:] < '60':\n",
    "                    ans = run\n",
    "                return\n",
    "            for i, r in enumerate(res):\n",
    "                backtrace(run+r, res[:i]+res[i+1:])\n",
    "        backtrace('', arr)\n",
    "        if ans:\n",
    "            return ans[0:2]+':'+ans[2:]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        hoursRes = -1\n",
    "        minsRes = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "                hoursRes = hours\n",
    "                minsRes = mins\n",
    "\n",
    "        return \"{:02}:{:02}\".format(hoursRes,minsRes) if ans >= 0 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        if min(arr) > 2:\n",
    "            return \"\"\n",
    "        max_time = -1\n",
    "        for perm in permutations(arr):\n",
    "            hours = perm[0] * 10 + perm[1]\n",
    "            minutes = perm[2] * 10 + perm[3]\n",
    "\n",
    "            if hours < 24 and minutes < 60:\n",
    "                total_minutes = hours * 60 + minutes\n",
    "                max_time = max(max_time, total_minutes)\n",
    "        \n",
    "        if max_time >= 0:\n",
    "            return f\"{max_time // 60:02d}:{max_time % 60:02d}\"\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        \n",
    "        def tonum(arr):\n",
    "            h = arr[0] * 10 + arr[1]\n",
    "            if -1 < h < 24:\n",
    "                m = arr[2] * 10 + arr[3]\n",
    "                if -1 < m < 60:\n",
    "                    return (h,m)\n",
    "            return (-1,-1)\n",
    "\n",
    "        def totime(x):\n",
    "            if x[0] < 0: return ''\n",
    "            return '%02d' % x[0] + ':' + '%02d' % x[1]\n",
    "        \n",
    "        t = sorted([tonum(x) for x in permutations(arr)])[-1]\n",
    "        return totime(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = ''\n",
    "        for a, b, c, d in permutations(map(str, arr)):\n",
    "            h = a + b\n",
    "            m = c + d\n",
    "            if '00' <= h < '24' and '00' <= m < '60':\n",
    "                cur = h + ':' + m\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestTimeFromDigits(self, A):\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(A):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestTimeFromDigits(self, A):\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(A):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = (-1, 0, 0, 0)\n",
    "        for time in permutations(arr, 4):\n",
    "            # 检查正确性\n",
    "            if time[0] > 2 or time[0] == 2 and time[1] > 3 or time[2] > 5:\n",
    "                continue\n",
    "            # 与答案比较\n",
    "            if time > ans:\n",
    "                ans = time\n",
    "\n",
    "        a, b, c, d = ans\n",
    "        if a == -1:\n",
    "            return ''\n",
    "        return f'{a}{b}:{c}{d}'\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = ''\n",
    "        for a in itertools.permutations(arr):\n",
    "            hour, minute = str(a[0]) + str(a[1]), str(a[2]) + str(a[3])\n",
    "            if hour <= '23' and minute <= '59':\n",
    "                ans = max(ans, str(hour) + ':' + str(minute))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = (-1, 0, 0, 0)\n",
    "        for time in permutations(arr):\n",
    "            # 检查正确性\n",
    "            if time[0] > 2 or time[0] == 2 and time[1] > 3 or time[2] > 5:\n",
    "                continue\n",
    "            # 与答案比较\n",
    "            if time > ans:\n",
    "                ans = time\n",
    "\n",
    "        a, b, c, d = ans\n",
    "        if a == -1:\n",
    "            return ''\n",
    "        return f'{a}{b}:{c}{d}'\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        perms = []\n",
    "        arr = sorted(arr)\n",
    "\n",
    "        def backtrace(nms, tmp):\n",
    "            if not nms:\n",
    "                perms.append(tmp)\n",
    "            \n",
    "            for i in range(len(nms)):\n",
    "                backtrace(nms[:i]+nms[i+1:], tmp+str(nms[i]))\n",
    "        backtrace(arr, '')\n",
    "        # print(perms)\n",
    "        perms = [p for p in perms if not (int(p[:2]) > 23 or int(p[2:]) > 59)]\n",
    "        if perms:\n",
    "            return perms[-1][:2]+':'+perms[-1][2:]\n",
    "        else:\n",
    "            return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort(reverse=True)\n",
    "        for a,  b, c, d in permutations(arr):\n",
    "            if a*10+b <24 and c*10+d<60:\n",
    "                return f\"{a}{b}:{c}{d}\"\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        A=[[0,1,2,3],[0,2,3,1],[0,3,1,2],[2,3,0,1],[3,1,0,2],[1,2,0,3]]\n",
    "        def check(i,j,b):\n",
    "            a1=-1\n",
    "            a2=-1\n",
    "            if b>=arr[i]*10+arr[j]>=0:\n",
    "                a1=arr[i]*10+arr[j]\n",
    "            if b>=arr[j]*10+arr[i]>=0:\n",
    "                a2=arr[j]*10+arr[i]\n",
    "            return max(a1,a2)\n",
    "        res=[]\n",
    "        for a in range(6):\n",
    "            i,j,k,l=A[a]\n",
    "            pp=check(i,j,23)\n",
    "            qq=check(k,l,59)\n",
    "            if pp==-1 or qq==-1:\n",
    "                continue\n",
    "            else:\n",
    "                res.append([pp,qq])\n",
    "        if not res:\n",
    "            return \"\"\n",
    "        an=sorted(res, key=lambda x:(x[0],x[1]))\n",
    "        [L,J]=an.pop()\n",
    "        if L<=9:\n",
    "            oo=\"0\"+str(L)\n",
    "        else:\n",
    "            oo=str(L)\n",
    "        if J<=9:\n",
    "            jj=\"0\"+str(J)\n",
    "        else:\n",
    "            jj=str(J)\n",
    "        return oo+\":\"+jj\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans=-1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(arr):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                    ans = time\n",
    "        return \"{:02d}:{:02d}\".format(ans//60,ans%60) if ans>=0 else ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plzh(self, arr):\n",
    "        ret = []\n",
    "        ls = []\n",
    "        def dfs(n):\n",
    "            if n == 0:\n",
    "                if ls[0] * 10 + ls[1] < 24 and ls[2] * 10 + ls[3] < 60:\n",
    "                    ret.append(f'{ls[0]}{ls[1]}:{ls[2]}{ls[3]}')\n",
    "                return\n",
    "            for i in range(n):\n",
    "                ls.append(arr[i])\n",
    "                arr[i], arr[n-1] = arr[n-1], arr[i]\n",
    "                dfs(n-1)\n",
    "                ls.pop()\n",
    "                arr[i], arr[n-1] = arr[n-1], arr[i]\n",
    "        dfs(4)\n",
    "        return ret\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        return max(chain([''], self.plzh(arr)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "\n",
    "        def backtrack(used):\n",
    "\n",
    "            if len(path) == len(arr) and 0 <= path[0] * 10 + path[1] < 24 and 0 <= path[2] * 10 + path[3] <= 59:\n",
    "                res.append(list(map(str, path.copy())))\n",
    "                return True\n",
    "            for i in range(len(arr)):\n",
    "                if used[i]: continue\n",
    "                path.append(arr[i])\n",
    "                used[i] = True\n",
    "                if backtrack(used):\n",
    "                    return True\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "\n",
    "        arr.sort(reverse=True)\n",
    "        path, res = [], []\n",
    "        used = [False for _ in range(len(arr))]\n",
    "        backtrack(used)\n",
    "\n",
    "        return \"\".join(res[0][:2]) + \":\" + \"\".join(res[0][2:]) if res else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        # arr.sort(reverse=True)\n",
    "        # for a,  b, c, d in permutations(arr):\n",
    "        #     if a*10+b <24 and c*10+d<60:\n",
    "        #         return f\"{a}{b}:{c}{d}\"\n",
    "        # return ''\n",
    "        res = max((i for i in itertools.permutations(arr) if 0 <= 10 * i[0] + i[1] <= 23 and 0 <= 10 * i[2] + i[3] <= 59), default = None)\n",
    "        if not res: return ''\n",
    "        return str(res[0]) + str(res[1]) + ':' + str(res[2]) + str(res[3])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        res = -1\n",
    "        for a, b, c, d in itertools.permutations(arr, 4):\n",
    "            if a * 10 + b < 24 and c * 10 + d < 60:\n",
    "                res = max(res, a*1000 + b*100 + c*10 + d)\n",
    "        return \"\" if res == -1 else \"{:02d}:{:02d}\".format(res // 100, res % 100) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr = set(list(itertools.permutations(arr)))\n",
    "        ans = -1\n",
    "        for x in arr:\n",
    "            hours = x[0]*10 + x[1]\n",
    "            mins = x[2]*10 + x[3]\n",
    "            if hours < 24 and mins < 60:\n",
    "                ans = max(ans,hours * 60 + mins)\n",
    "        \n",
    "        return '{:02}:{:02}'.format(*divmod(ans,60)) if ans >= 0 else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        def dfs(arr, path, res):\n",
    "            if not arr:\n",
    "                res.append(path.copy())\n",
    "                return \n",
    "            for i in range(len(arr)):\n",
    "                dfs(arr[:i]+arr[i+1:], path+[arr[i]], res)\n",
    "        arr.sort(reverse=True)\n",
    "        res = []\n",
    "        dfs(arr, [], res)\n",
    "        ans = []\n",
    "        for a, b, c, d in res:\n",
    "            if 10*a+b < 24 and 10*c+d<60:\n",
    "                ans.append([a, b, c, d]) \n",
    "        ans.sort()\n",
    "        return str(ans[-1][0]) + str(ans[-1][1]) + \":\" + str(ans[-1][2]) + str(ans[-1][3])   if ans else \"\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        count_wrong = 0\n",
    "        bigger = []\n",
    "        small = []\n",
    "        for item in arr:\n",
    "            if item >= 6:\n",
    "                count_wrong += 1\n",
    "                bigger.append(item)\n",
    "            else:\n",
    "                small.append(item)\n",
    "\n",
    "        if count_wrong > 2:\n",
    "            return \"\"\n",
    "        elif count_wrong == 2:\n",
    "            second = max(bigger)\n",
    "            fourth = min(bigger)\n",
    "            if 1 in arr:\n",
    "                first = 1\n",
    "            elif 0 in arr:\n",
    "                first = 0\n",
    "            else:\n",
    "                return \"\"\n",
    "            for i in range(2):\n",
    "                if small[i] == first:\n",
    "                    del small[i]\n",
    "                    break\n",
    "            third = small[0]\n",
    "            return \"%d%d:%d%d\" % (first, second, third, fourth)\n",
    "\n",
    "        if 2 in arr:\n",
    "            first = 2\n",
    "        elif 1 in arr:\n",
    "            first = 1\n",
    "        elif 0 in arr:\n",
    "            first = 0\n",
    "        else:\n",
    "            return \"\"\n",
    "        \n",
    "        for i in range(4):\n",
    "            if arr[i] == first:\n",
    "                del arr[i]\n",
    "                break\n",
    "\n",
    "        if first in [0, 1]:\n",
    "            second = max(arr)\n",
    "        else:\n",
    "            if 3 in arr:\n",
    "                second = 3\n",
    "            elif 2 in arr:\n",
    "                second = 2\n",
    "            elif 1 in arr:\n",
    "                second = 1\n",
    "            elif 0 in arr:\n",
    "                second = 0\n",
    "            else:\n",
    "                return \"\"\n",
    "\n",
    "        for i in range(3):\n",
    "            if arr[i] == second:\n",
    "                del arr[i]\n",
    "                break\n",
    "\n",
    "        if 5 in arr:\n",
    "            third = 5\n",
    "        elif 4 in arr:\n",
    "            third = 4\n",
    "        elif 3 in arr:\n",
    "            third = 3\n",
    "        elif 2 in arr:\n",
    "            third = 2\n",
    "        elif 1 in arr:\n",
    "            third = 1\n",
    "        elif 0 in arr:\n",
    "            third = 0\n",
    "        else:\n",
    "            return \"\"\n",
    "\n",
    "        for i in range(2):\n",
    "            if arr[i] == third:\n",
    "                del arr[i]\n",
    "                break\n",
    "\n",
    "        fourth = arr[0]\n",
    "\n",
    "        return \"%d%d:%d%d\" % (first, second, third, fourth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        # arr.sort(reverse=True)\n",
    "        # for a,  b, c, d in permutations(arr):\n",
    "        #     if a*10+b <24 and c*10+d<60:\n",
    "        #         return f\"{a}{b}:{c}{d}\"\n",
    "        # return ''\n",
    "        res = max((i for i in permutations(arr) if 0 <= 10 * i[0] + i[1] <= 23 and 0 <= 10 * i[2] + i[3] <= 59), default = None)\n",
    "        if not res: return ''\n",
    "        return str(res[0]) + str(res[1]) + ':' + str(res[2]) + str(res[3])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = []\n",
    "        temp = []\n",
    "        def dfs(arr):\n",
    "            nonlocal ans\n",
    "            if not arr:\n",
    "                hour, minute = temp[0]*10 + temp[1], temp[2]*10 + temp[3]\n",
    "                if hour <= 23 and minute <= 59:\n",
    "                    if not ans or ans[0] < hour or (ans[0] == hour and ans[1] < minute):\n",
    "                        ans = [hour, minute]\n",
    "                return\n",
    "            \n",
    "            for i in range(len(arr)):\n",
    "                temp.append(arr[i])\n",
    "                dfs(arr[:i] + arr[i+1:])\n",
    "                temp.pop()\n",
    "        dfs(arr)\n",
    "        if not ans: return \"\"\n",
    "        ans[0] = \"0\" + str(ans[0]) if ans[0] <= 9 else str(ans[0])\n",
    "        ans[1] = \"0\" + str(ans[1]) if ans[1] <= 9 else str(ans[1])\n",
    "        return \":\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestTimeFromDigits(self, A):\n",
    "        ans = -1\n",
    "        for h1, h2, m1, m2 in itertools.permutations(A):\n",
    "            hours = 10 * h1 + h2\n",
    "            mins = 10 * m1 + m2\n",
    "            time = 60 * hours + mins\n",
    "            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:\n",
    "                ans = time\n",
    "\n",
    "        return \"{:02}:{:02}\".format(*divmod(ans, 60)) if ans >= 0 else \"\"\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        max_t = -1\n",
    "        ans = None\n",
    "        for h1, h2, m1, m2 in permutations(arr):\n",
    "            h = h1 * 10 + h2\n",
    "            m = m1 * 10 + m2\n",
    "            if h > 23 or m > 59:\n",
    "                continue\n",
    "            t = h * 60 + m\n",
    "            if t > max_t:\n",
    "                max_t, ans = t, (h, m)\n",
    "        if ans is None:\n",
    "            return \"\"\n",
    "        return f\"{ans[0]:02d}:{ans[1]:02d}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        n = len(arr)\n",
    "        ans = ''\n",
    "        mx = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    for q in range(n):\n",
    "                        if i != j and i != k and i != q and j != k and j != q and k != q:\n",
    "                            if int(str(arr[i]) + str(arr[j])) > 23 or int(str(arr[k]) + str(arr[q])) > 59:\n",
    "                                continue\n",
    "                            times = int(str(arr[i]) + str(arr[j]) + str(arr[k]) + str(arr[q]))\n",
    "                            if times > mx:\n",
    "                                mx = times\n",
    "                                ans = str(arr[i]) + str(arr[j]) + ':' + str(arr[k]) + str(arr[q])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        self.ans, rem = -1, {0, 1, 2, 3}\n",
    "        def dfs(idx, tmp):\n",
    "            if idx == 4: self.ans = max(self.ans, tmp)\n",
    "            else:\n",
    "                for v in range(4):\n",
    "                    if v in rem:\n",
    "                        rem.remove(v)\n",
    "                        new = tmp * 10 + arr[v]\n",
    "                        if idx == 0 and arr[v] < 3: dfs(idx + 1, new)\n",
    "                        elif idx == 1 and new < 24: dfs(idx + 1, new)\n",
    "                        elif idx == 2 and arr[v] < 6: dfs(idx + 1, new)\n",
    "                        elif idx == 3 and new % 100 < 60: dfs(idx + 1, new)\n",
    "                        rem.add(v)\n",
    "        dfs(0, 0)\n",
    "        if self.ans < 0: return ''\n",
    "        p1, p2 = str(self.ans // 100), str(self.ans % 100)\n",
    "        if len(p1) == 1: p1 = '0' + p1\n",
    "        if len(p2) == 1: p2 = '0' + p2\n",
    "        return p1 + ':' + p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = []\n",
    "        temp = []\n",
    "        def dfs(arr):\n",
    "            nonlocal ans\n",
    "            if not arr:\n",
    "                hour, minute = temp[0]*10 + temp[1], temp[2]*10 + temp[3]\n",
    "                if hour <= 23 and minute <= 59:\n",
    "                    if not ans or ans[0] < hour or (ans[0] == hour and ans[1] < minute):\n",
    "                        ans = [hour, minute]\n",
    "                return\n",
    "            \n",
    "            for i in range(len(arr)):\n",
    "                temp.append(arr[i])\n",
    "                dfs(arr[:i] + arr[i+1:])\n",
    "                temp.pop()\n",
    "        dfs(arr)\n",
    "        if not ans: return \"\"\n",
    "        ans[0] = \"0\" + str(ans[0]) if ans[0] <= 9 else str(ans[0])\n",
    "        ans[1] = \"0\" + str(ans[1]) if ans[1] <= 9 else str(ans[1])\n",
    "        return \":\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = []\n",
    "        temp = []\n",
    "        def dfs(arr):\n",
    "            nonlocal ans\n",
    "            if not arr:\n",
    "                hour, minute = temp[0]*10 + temp[1], temp[2]*10 + temp[3]\n",
    "                if hour <= 23 and minute <= 59:\n",
    "                    if not ans or ans[0] < hour or (ans[0] == hour and ans[1] < minute):\n",
    "                        ans = [hour, minute]\n",
    "                return\n",
    "            \n",
    "            for i in range(len(arr)):\n",
    "                temp.append(arr[i])\n",
    "                dfs(arr[:i] + arr[i+1:])\n",
    "                temp.pop()\n",
    "        dfs(arr)\n",
    "        if not ans: return \"\"\n",
    "        ans[0] = \"0\" + str(ans[0]) if ans[0] <= 9 else str(ans[0])\n",
    "        ans[1] = \"0\" + str(ans[1]) if ans[1] <= 9 else str(ans[1])\n",
    "        return \":\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        res_str=\"\"\n",
    "        sset=set()\n",
    "        def dfs(cur,temp):\n",
    "            nonlocal res_str\n",
    "            if cur==4:\n",
    "                if len(res_str)==0:\n",
    "                    res_str=temp\n",
    "                else:\n",
    "                    print(res_str)\n",
    "                    if temp>res_str:\n",
    "                        res_str=temp\n",
    "                return\n",
    "            for i in range(0, len(arr)):\n",
    "                if cur==0 and arr[i]<=2 and i not in sset:\n",
    "                    sset.add(i)\n",
    "                    dfs(cur+1, temp+str(arr[i]))\n",
    "                    sset.remove(i)\n",
    "                elif cur==1 and i not in sset:\n",
    "                    if temp[cur-1]=='2':\n",
    "                        if arr[i]<=3:\n",
    "                            sset.add(i)\n",
    "                            dfs(cur+1, temp+str(arr[i]))\n",
    "                            sset.remove(i)\n",
    "                    else:\n",
    "                        sset.add(i)\n",
    "                        dfs(cur+1, temp+str(arr[i]))\n",
    "                        sset.remove(i)\n",
    "                elif cur==2 and arr[i]<=5 and i not in sset:\n",
    "                    sset.add(i)\n",
    "                    dfs(cur+1, temp+str(arr[i]))\n",
    "                    sset.remove(i)\n",
    "                elif cur==3 and i not in sset:\n",
    "                    sset.add(i)\n",
    "                    dfs(cur+1, temp+str(arr[i]))\n",
    "                    sset.remove(i)\n",
    "                \n",
    "        dfs(0,\"\")\n",
    "        if res_str==\"\":\n",
    "            return res_str\n",
    "        res_str=res_str[:2]+':'+res_str[2:]\n",
    "        return res_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\r\n",
    "        ans = (-1, 0, 0, 0)\r\n",
    "        for time in permutations(arr):\r\n",
    "            if time[0] > 2 or time[0] == 2 and time[1] > 3 or time[2] > 5:\r\n",
    "                continue\r\n",
    "            if time > ans:\r\n",
    "                ans = time\r\n",
    "        if ans[0] == -1:\r\n",
    "            return \"\"\r\n",
    "        else:\r\n",
    "            return \"{}{}:{}{}\".format(*ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        n=len(arr)\n",
    "        flag=0\n",
    "        ans=\"00:00\"\n",
    "        def f(st):\n",
    "            if len(st)==n:\n",
    "                h=int(\"\".join(st[:2]))\n",
    "                m=int(\"\".join(st[2:]))\n",
    "                if 0<=h<=23 and 0<=m<=59:\n",
    "                    nonlocal flag\n",
    "                    flag=1\n",
    "                    nonlocal ans\n",
    "                    if h>int(ans[:2]):\n",
    "                        ans=\"{:0>2}:{:0>2}\".format(h,m)\n",
    "                    elif h==int(ans[:2]) and m>int(ans[3:]):\n",
    "                        ans=\"{:0>2}:{:0>2}\".format(h,m)\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if not vis[i]:\n",
    "                    st.append(str(arr[i]))\n",
    "                    vis[i]=True\n",
    "                    f(st)\n",
    "                    st.pop()\n",
    "                    vis[i]=False\n",
    "        for i in range(n):\n",
    "            vis=[False]*n\n",
    "            vis[i]=True\n",
    "            f([str(arr[i])])\n",
    "        if flag:\n",
    "            return ans\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "\n",
    "        ava_list = []\n",
    "\n",
    "        def convert(s):\n",
    "            s_hour = int(s[:2])\n",
    "            s_min = int(s[2:])\n",
    "            return s_hour, s_min\n",
    "\n",
    "        def legal(hour, minute):\n",
    "            if 0 <= hour <= 23 and 0 <= minute <= 59:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def compare_bigger(s1, s2):\n",
    "            s1_h, s1_m = convert(s1)\n",
    "            s2_h, s2_m = convert(s2)\n",
    "            if s1_h > s2_h or (s1_h == s2_h and s1_m > s2_m):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def dfs(mask, now_str):\n",
    "            if mask == 15:\n",
    "                if legal(*convert(now_str)):\n",
    "                    ava_list.append(now_str)\n",
    "                return\n",
    "            for i in range(4):\n",
    "                if mask & 1 << i == 0:\n",
    "                    dfs(mask | 1 << i, now_str + str(arr[i]))\n",
    "\n",
    "        dfs(0, \"\")\n",
    "\n",
    "\n",
    "\n",
    "        if len(ava_list) == 0:\n",
    "            return \"\"\n",
    "        result = ava_list[0]\n",
    "        for i in range(1, len(ava_list)):\n",
    "            if compare_bigger(ava_list[i], result):\n",
    "                result = ava_list[i]\n",
    "        return result[:2] + ':' + result[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        MAX = -1\n",
    "        a = 0\n",
    "        b = 0\n",
    "        c = 0\n",
    "        d = 0\n",
    "        for i,j,k,l in permutations(arr):\n",
    "            hours = i*10+j\n",
    "            mins = k*10+l\n",
    "            ans = 60*hours + mins\n",
    "            if ans>MAX and hours<24 and mins<60:\n",
    "                MAX = ans\n",
    "                a = i\n",
    "                b = j\n",
    "                c = k\n",
    "                d = l\n",
    "        if MAX!=-1:\n",
    "            return str(a)+str(b)+':'+str(c)+str(d)\n",
    "        else:\n",
    "            return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort(reverse=True)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j:\n",
    "                    for k in range(n):\n",
    "                        if k!= i and k!=j:\n",
    "                            v = 6 - i - j -k\n",
    "                            if arr[i] <= 1 and arr[k] <= 5 or \\\n",
    "                                arr[i] == 2 and arr[j] <= 3 and arr[k] <= 5:\n",
    "                                ans = '{}{}:{}{}'.format(arr[i],arr[j],arr[k],arr[v])\n",
    "                                return ans \n",
    "\n",
    "        return \"\" \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort()\n",
    "        book = [0]*4\n",
    "        def backtracking(start):\n",
    "            if(start == 4):\n",
    "                self.result.append(self.path[:])\n",
    "                return\n",
    "            for i in range(4):\n",
    "                if(book[i] == 1):\n",
    "                    continue\n",
    "                if(i > 0 and arr[i-1] == arr[i] and book[i-1] == 0):\n",
    "                    continue\n",
    "                book[i] = 1\n",
    "                self.path.append(arr[i])\n",
    "                backtracking(start+1)\n",
    "                book[i] = 0\n",
    "                self.path.pop()\n",
    "            return\n",
    "        backtracking(0)\n",
    "        maxs = -1\n",
    "        result = \"\"\n",
    "        for h1,h2,m1,m2 in self.result:\n",
    "            h = h1*10+h2 \n",
    "            m = m1*10+m2 \n",
    "            if(h >= 24 or m >= 60):\n",
    "                continue\n",
    "            if(h*60+m > maxs):\n",
    "                maxs = h*60+m\n",
    "                result = str(h1)+str(h2)+':'+str(m1)+str(m2)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        \n",
    "        def tonum(arr):\n",
    "            h = arr[0] * 10 + arr[1]\n",
    "            if -1 < h < 24:\n",
    "                m = arr[2] * 10 + arr[3]\n",
    "                if -1 < m < 60:\n",
    "                    return (h,m)\n",
    "            return (-1,-1)\n",
    "\n",
    "        def totime(x):\n",
    "            if x[0] < 0: return ''\n",
    "            h = str(x[0]) if x[0]>= 10 else '0' + str(x[0])\n",
    "            m = str(x[1]) if x[1]>= 10 else '0' + str(x[1])\n",
    "            return h + ':' + m\n",
    "        \n",
    "        t = sorted([tonum(x) for x in permutations(arr)])[-1]\n",
    "        return totime(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        total = []\n",
    "        str_arr = ''.join(list(map(str, arr)))\n",
    "\n",
    "        def dfs(s, curr):\n",
    "            if not s:\n",
    "                total.append(curr)\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                dfs(s[:i] + s[i+1:], curr + s[i])\n",
    "\n",
    "        dfs(str_arr, '')\n",
    "        total.sort(reverse=True)\n",
    "        for item in total:\n",
    "            if int(item[:2]) < 24 and int(item[2:]) < 60:\n",
    "                return item[:2] + \":\" + item[2:]\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        def dfs(arr, path, res):\n",
    "            if not arr:\n",
    "                res.append(path.copy())\n",
    "                return \n",
    "            for i in range(len(arr)):\n",
    "                dfs(arr[:i]+arr[i+1:], path+[arr[i]], res)\n",
    "        arr.sort(reverse=True)\n",
    "        res = []\n",
    "        dfs(arr, [], res)\n",
    "        for a, b, c, d in res:\n",
    "            if 10*a+b < 24 and 10*c+d<60:\n",
    "                return str(a) + str(b) +':' + str(c) + str(d)\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        def getmin(a, b, c, d) -> int:\n",
    "            hour = a * 10 + b\n",
    "            minute = c * 10 + d\n",
    "            ans = hour * 60 + minute\n",
    "            if hour < 24 and minute < 60 and ans < 1440:\n",
    "                return ans\n",
    "            return -1\n",
    "        ans = -1\n",
    "        res = \"\"\n",
    "        for a, b, c, d in permutations(arr, 4):\n",
    "            temp = getmin(a, b, c, d)\n",
    "            if temp > ans:\n",
    "                ans = temp\n",
    "                res = str(a) + str(b) + ':' + str(c) + str(d)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        ans = []\n",
    "        temp = []\n",
    "        def dfs(arr):\n",
    "            nonlocal ans\n",
    "            if not arr:\n",
    "                hour, minute = temp[0]*10 + temp[1], temp[2]*10 + temp[3]\n",
    "                if hour <= 23 and minute <= 59:\n",
    "                    if not ans or ans[0] < hour or (ans[0] == hour and ans[1] < minute):\n",
    "                        ans = [hour, minute]\n",
    "                return\n",
    "            \n",
    "            for i in range(len(arr)):\n",
    "                temp.append(arr[i])\n",
    "                dfs(arr[:i] + arr[i+1:])\n",
    "                temp.pop()\n",
    "        dfs(arr)\n",
    "        if not ans: return \"\"\n",
    "        ans[0] = \"0\" + str(ans[0]) if ans[0] <= 9 else str(ans[0])\n",
    "        ans[1] = \"0\" + str(ans[1]) if ans[1] <= 9 else str(ans[1])\n",
    "        return \":\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        arr.sort()\n",
    "        book = [0]*4\n",
    "        def backtracking(start):\n",
    "            if(start == 4):\n",
    "                self.result.append(self.path[:])\n",
    "                return\n",
    "            for i in range(4):\n",
    "                if(book[i] == 1):\n",
    "                    continue\n",
    "                if(i > 0 and arr[i-1] == arr[i] and book[i-1] == 0):\n",
    "                    continue\n",
    "                book[i] = 1\n",
    "                self.path.append(arr[i])\n",
    "                backtracking(start+1)\n",
    "                book[i] = 0\n",
    "                self.path.pop()\n",
    "            return\n",
    "        backtracking(0)\n",
    "        maxs = -1\n",
    "        result = \"\"\n",
    "        for h1,h2,m1,m2 in self.result:\n",
    "            h = h1*10+h2 \n",
    "            m = m1*10+m2 \n",
    "            if(h >= 24 or m >= 60):\n",
    "                continue\n",
    "            if(h*60+m > maxs):\n",
    "                maxs = h*60+m\n",
    "                result = str(h1)+str(h2)+':'+str(m1)+str(m2)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTimeFromDigits(self, arr: List[int]) -> str:\n",
    "        count_wrong = 0\n",
    "        bigger = []\n",
    "        small = []\n",
    "        for item in arr:\n",
    "            if item >= 6:\n",
    "                count_wrong += 1\n",
    "                bigger.append(item)\n",
    "            else:\n",
    "                small.append(item)\n",
    "        print(bigger,small)\n",
    "        print(count_wrong)\n",
    "\n",
    "        if count_wrong > 2:\n",
    "            return \"\"\n",
    "        elif count_wrong == 2:\n",
    "            second = max(bigger)\n",
    "            fourth = min(bigger)\n",
    "            if 1 in arr:\n",
    "                first = 1\n",
    "            elif 0 in arr:\n",
    "                first = 0\n",
    "            else:\n",
    "                return \"\"\n",
    "            for i in range(2):\n",
    "                if small[i] == first:\n",
    "                    del small[i]\n",
    "                    break\n",
    "            third = small[0]\n",
    "            return \"%d%d:%d%d\" % (first, second, third, fourth)\n",
    "\n",
    "        if 2 in arr:\n",
    "            first = 2\n",
    "        elif 1 in arr:\n",
    "            first = 1\n",
    "        elif 0 in arr:\n",
    "            first = 0\n",
    "        else:\n",
    "            return \"\"\n",
    "        \n",
    "        for i in range(4):\n",
    "            if arr[i] == first:\n",
    "                del arr[i]\n",
    "                break\n",
    "        print(arr)\n",
    "        if first in [0, 1]:\n",
    "            second = max(arr)\n",
    "        else:\n",
    "            if 3 in arr:\n",
    "                second = 3\n",
    "            elif 2 in arr:\n",
    "                second = 2\n",
    "            elif 1 in arr:\n",
    "                second = 1\n",
    "            elif 0 in arr:\n",
    "                second = 0\n",
    "            else:\n",
    "                return \"\"\n",
    "        print(second)\n",
    "        for i in range(3):\n",
    "            if arr[i] == second:\n",
    "                del arr[i]\n",
    "                break\n",
    "        print(arr)\n",
    "        if 5 in arr:\n",
    "            third = 5\n",
    "        elif 4 in arr:\n",
    "            third = 4\n",
    "        elif 3 in arr:\n",
    "            third = 3\n",
    "        elif 2 in arr:\n",
    "            third = 2\n",
    "        elif 1 in arr:\n",
    "            third = 1\n",
    "        elif 0 in arr:\n",
    "            third = 0\n",
    "        else:\n",
    "            return \"\"\n",
    "        print(arr)\n",
    "        for i in range(2):\n",
    "            if arr[i] == third:\n",
    "                del arr[i]\n",
    "                break\n",
    "\n",
    "        fourth = arr[0]\n",
    "\n",
    "        return \"%d%d:%d%d\" % (first, second, third, fourth)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
